
/*
 * template implementation of the stack data structure and operations on stack.
 * Controlled by the following macro definitions:
 *
 * required macros:
 *  QL_STACK_ELEMENT_TYPE - defines element type
 *  QL_STACK_XREALLOC - defines memory reallocation function, that will never return 0
 *  QL_STACK_XFREE - defines memory releasing function
 *
 * optional macros:
 *  QL_STACK_NS - namespace macro
 *  QL_STACK_ASSERT - specifies user-level assert macro
 *  QL_STACK_GROW_SIZE - specifies grow size constant that is used to recalculate reallocation size
 *  QL_STACK_PREALLOCATED_SIZE - specifies that stack has preallocated part that
 *                               comes as a part of the stack structure
 *                               this can result in a benefit when using Stack as a local variable
 *
 * unmasked types/functions:
 *  Stack
 *  stack_init
 *  stack_uninit
 *  stack_push
 *  stack_pop
 *  stack_empty
 *
 * A. Shabanov, 2008-2009
 */

#ifndef QL_STACK_NS
#define QL_STACK_NS(name) name
#endif

#ifndef QL_STACK_ELEMENT_TYPE
#error QL_STACK_ELEMENT_TYPE is not defined
#endif

#ifndef QL_STACK_XREALLOC
#error QL_STACK_XREALLOC is not been defined
#endif

#ifndef QL_STACK_XFREE
#error QL_STACK_XFREE is not been defined
#endif

#ifndef QL_STACK_ASSERT
#include <assert.h>
#define QL_STACK_ASSERT(x) assert(x)
#endif

#ifndef QL_STACK_GROW_SIZE
#define QL_STACK_GROW_SIZE  (256)
#endif

typedef struct
{
#ifdef QL_STACK_PREALLOCATED_SIZE
    QL_STACK_ELEMENT_TYPE   prealloc_elements[QL_STACK_PREALLOCATED_SIZE];
#endif

    QL_STACK_ELEMENT_TYPE * elements;

    size_t                  allocated;
    size_t                  size;
} QL_STACK_NS(Stack);

static void QL_STACK_NS(stack_init)(QL_STACK_NS(Stack) * stack)
{
    stack->elements = NULL;
    stack->allocated = 0;
    stack->size = 0;
}

static void QL_STACK_NS(stack_uninit)(QL_STACK_NS(Stack) * stack)
{
    QL_STACK_XFREE(stack->elements);
}

static void QL_STACK_NS(stack_push)(QL_STACK_NS(Stack) * stack, QL_STACK_ELEMENT_TYPE element)
{
#ifdef QL_STACK_PREALLOCATED_SIZE
    if (stack->size < QL_STACK_PREALLOCATED_SIZE)
    {
        /* element can be placed into the preallocated stack */
        stack->prealloc_elements[stack->size] = element;
    }
    else
    {
        /* place element into the allocated array */
        size_t alloc_size = stack->size - QL_STACK_PREALLOCATED_SIZE;

        if ((alloc_size + 1) > stack->allocated)
        {
            stack->allocated += QL_STACK_GROW_SIZE;
            stack->elements = QL_STACK_XREALLOC(stack->elements, sizeof(QL_STACK_ELEMENT_TYPE) * stack->allocated);
        }

        stack->elements[alloc_size] = element;
    }

    stack->size++;
#else
    if ((stack->size + 1) > stack->allocated)
    {
        stack->allocated += QL_STACK_GROW_SIZE;
        stack->elements = QL_STACK_XREALLOC(stack->elements, sizeof(QL_STACK_ELEMENT_TYPE) * stack->allocated);
    }

    stack->elements[stack->size++] = element;
#endif
}

static QL_STACK_ELEMENT_TYPE QL_STACK_NS(stack_pop)(QL_STACK_NS(Stack) * stack)
{
    QL_STACK_ELEMENT_TYPE element;
    QL_STACK_ASSERT(stack->size > 0);

#ifdef QL_STACK_PREALLOCATED_SIZE
    --stack->size;

    if (stack->size < QL_STACK_PREALLOCATED_SIZE)
    {
        element = stack->prealloc_elements[stack->size];
    }
    else
    {
        element = stack->elements[stack->size - QL_STACK_PREALLOCATED_SIZE];
    }
#else
    element = stack->elements[--stack->size];
#endif

    return element;
}

static bool QL_STACK_NS(stack_empty)(QL_STACK_NS(Stack) * stack)
{
    return (stack->size == 0);
}

/*
 * undefine user macros
 */
#undef QL_STACK_ELEMENT_TYPE
#undef QL_STACK_XREALLOC
#undef QL_STACK_XFREE
#undef QL_STACK_NS
#undef QL_STACK_ASSERT
#undef QL_STACK_GROW_SIZE
#undef QL_STACK_PREALLOCATED_SIZE
